package leecode

func zigzagLevelOrder(root *TreeNode) (result [][]int) {
	//检查根节点
	if root == nil {
		return
	}
	dqueue := []*TreeNode{root}
	flag := 0 //奇数层需要反转
	for len(dqueue) != 0 {
		temp := make([]int, 0)
		size := len(dqueue) //固定每一层的长度
		for i := 0; i < size; i++ {
			temp = append(temp, dqueue[i].Val)
			//将当前节点的左节点和右节点加入队列
			if dqueue[i].Left != nil {
				dqueue = append(dqueue, dqueue[i].Left)
			}
			if dqueue[i].Right != nil {
				dqueue = append(dqueue, dqueue[i].Right)
			}
		}
		//每一层遍历完成,改变方向
		if flag%2 == 1 {
			//反转数组
			for i, n := 0, len(temp); i < n/2; i++ {
				temp[i], temp[n-1-i] = temp[n-1-i], temp[i]
			}
		}
		//弹出队列中的所有父节点
		dqueue = dqueue[size:]
		result = append(result, temp)
		flag++
	}
	return
}
